package com.example.zz.example.datastructures.nowcoder;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: zhuozhang6
 * @date: 2021/12/1
 * @email: zhuozhang6@iflytek.com
 * @Description:
 */
public class TreeOffer {
    private static TreeNode mTreeNode;

    public static void main(String[] args) {

        //二叉树中，和为某一值的路径2
        findPathProblem();

        //二叉树中，和为某一值的路径
        hasPathSumProblem();

        //判断是否为二叉搜索树后序遍历
        houxuCheckOfBSTProblem();

        //二叉树的镜像
        mirrorProblem();

        //判断是否为子树
        hasSubTreeProblem();

        //重建二叉树
        reConstructBinaryTreeProblem();

        //二叉搜索树的第k个节点
        searchTreeFindKProblem();

        //之字形打印
        zhiPrintProblem();

        //二叉树的深度
        treeDepthProblem();

        //初始化树
        initTreeNode();
        //前序遍历
        qianXuProblem();
        //中序遍历
        zhongXuProblem();
        //后序遍历
        houXuProblem();
        //层序遍历
        cengXuProblem();
    }

    private static void findPathProblem() {

        /**
         * 输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
         * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
         * 2.叶子节点是指没有子节点的节点
         * 3.路径只能从父节点到子节点，不能从子节点到父节点
         * 4.总节点数目为n
         */

        /**
         * 树结构
         *          10
         *        /   \
         *      5      12
         *    /  \
         *   4    7
         */
        TreeNode treeNode = new TreeNode(10);
        TreeNode treeNode2 = new TreeNode(5);
        TreeNode treeNode3 = new TreeNode(12);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;

        ArrayList<ArrayList<Integer>> b = findPath(treeNode, 22);
        System.out.println("是否有从根节点到叶子节点的节点值之和等于 sum 的路径：" + b);
    }

    private static ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
    private static ArrayList<Integer> list = new ArrayList();
    private static ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
        if (root == null) {
            return listAll;
        }
        list.add(root.val);
        target = target - root.val;
        if (target == 0 && root.left == null && root.right == null){
            listAll.add(new ArrayList(list));
        }
        findPath(root.left, target);
        findPath(root.right, target);
        list.remove(list.size() - 1);
        return listAll;
    }


    private static void hasPathSumProblem() {

        /**
         * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
         * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
         * 2.叶子节点是指没有子节点的节点
         * 3.路径只能从父节点到子节点，不能从子节点到父节点
         * 4.总节点数目为n
         */

        /**
         * 树结构
         *          5
         *        /   \
         *      4      8
         *    /  \      \
         *   1    11     9
         *       /  \
         *     2     7
         */
        TreeNode treeNode = new TreeNode(5);
        TreeNode treeNode2 = new TreeNode(4);
        TreeNode treeNode3 = new TreeNode(8);
        TreeNode treeNode4 = new TreeNode(1);
        TreeNode treeNode5 = new TreeNode(11);
        TreeNode treeNode6 = new TreeNode(9);
        TreeNode treeNode7 = new TreeNode(2);
        TreeNode treeNode8 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.right = treeNode6;
        treeNode5.left = treeNode7;
        treeNode5.right = treeNode8;
        boolean b = hasPathSum(treeNode, 22);
        System.out.println("是否有从根节点到叶子节点的节点值之和等于 sum 的路径：" + b);
    }

    /**
     * 有一个子树是true就是true，用||可以实现
     *
     * @param treeNode
     * @param sum
     * @return
     */
    private static boolean hasPathSum(TreeNode treeNode, int sum) {
        if (treeNode == null) {
            return false;
        }
        if (treeNode.left == null && treeNode.right == null && treeNode.val == sum) {
            return true;
        }
        sum = sum - treeNode.val;
        return hasPathSum(treeNode.left, sum) || hasPathSum(treeNode.right, sum);
    }

    private static void houxuCheckOfBSTProblem() {
        /**
         * 判断数组是否为搜索树的后序遍历
         * 搜索树满足左子树的元素都小于根节点，右子树的元素都大于根节点
         * 后序遍历的顺序为左子树->右子树->根节点
         */
        int[] ints = {5, 7, 6, 9, 11, 10, 8};
        boolean b = houxuCheckOfBST(ints);
        System.out.println("数组是否为搜索树的后序遍历：" + b);
    }

    boolean isHouxu = true;

    private static boolean houxuCheckOfBST(int[] seq) {
        int root = seq[seq.length - 1];
        int[] start = Arrays.copyOfRange(seq, 0, seq.length / 2);
        int[] end = Arrays.copyOfRange(seq, seq.length / 2, seq.length - 1);

        return false;
    }

    private static void mirrorProblem() {
        /**
         * 将树进行镜像
         *
         *          8
         *        /   \
         *      6      10
         *    /  \   /  \
         *   5    7 9    11
         *
         *  变为
         *          8
         *        /   \
         *     10      6
         *    /  \   /  \
         *  11    9 7    5
         *
         */
        TreeNode treeNode = new TreeNode(8);
        TreeNode treeNode2 = new TreeNode(6);
        TreeNode treeNode3 = new TreeNode(10);
        TreeNode treeNode4 = new TreeNode(5);
        TreeNode treeNode5 = new TreeNode(7);
        TreeNode treeNode6 = new TreeNode(9);
        TreeNode treeNode7 = new TreeNode(11);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;

        TreeNode mirroredTree = mirror(treeNode);

        printTreeUtil(mirroredTree);
    }

    private static TreeNode mirror(TreeNode root) {
        if (root == null) {
            return root;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            if (node.left != null || node.right != null) {
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
        }
        return root;
    }


    private static void hasSubTreeProblem() {
        /**
         * 两个数，判断其中一个是否为另一个的子树
         */

        TreeNode treeNode = new TreeNode(8);
        TreeNode treeNode2 = new TreeNode(8);
        TreeNode treeNode3 = new TreeNode(7);
        TreeNode treeNode4 = new TreeNode(9);
        TreeNode treeNode5 = new TreeNode(2);
        TreeNode treeNode6 = new TreeNode(4);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode5.left = treeNode6;
        treeNode5.right = treeNode7;

        TreeNode root = new TreeNode(8);
        TreeNode root2 = new TreeNode(9);
        TreeNode root3 = new TreeNode(2);
        root.left = root2;
        root.right = root3;

        hasSubTree(treeNode, root);
    }

    //第一：递归实现：20ms
    private static boolean hasSubTree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        boolean b = isSame(root1, root2) || isSame(root1.left, root2) || isSame(root1.right, root2);
        return b;
    }

    public static boolean isSame(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        return root1.val == root2.val && isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
    }

    //第二：非递归实现：广度优先遍历判断 14ms
    public boolean hasSubTree2(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root1);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (isSame(cur, root2)) return true;
            else {
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return false;
    }

    private static void reConstructBinaryTreeProblem() {
        /**
         * 已知前序中序遍历，重建二叉树
         */

        int[] pre = {1, 2, 3, 4, 5, 6, 7};
        int[] vin = {3, 2, 4, 1, 6, 5, 7};

        TreeNode treeNode = reConstructBinaryTree(pre, vin);
    }

    private static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }

    private static void searchTreeFindKProblem() {
        /**
         * 给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
         *
         * BST: 二叉搜索树，二叉查找树，二叉排序树
         * 1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
         * 2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
         * 3.任意结点的左、右子树也分别为二叉搜索树。
         *
         * 中序遍历时，顺序是从小到大的出现
         *          5
         *        /   \
         *      3      7
         *    /  \   /  \
         *   2    4 6    8
         */

        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(8);
        treeNode5.left = treeNode3;
        treeNode5.right = treeNode7;
        treeNode7.left = treeNode6;
        treeNode7.right = treeNode8;
        treeNode3.left = treeNode2;
        treeNode3.right = treeNode4;
        int k = 3;
        int value = KthNode(treeNode5, k);
        System.out.printf("搜索树第k小值：" + value);
        System.out.println();
    }

    private static int KthNode(TreeNode treeNode, int k) {
        if (treeNode == null) {
            return -1;
        }
        mK = k;
        searchTree(treeNode);
        return mValue;
    }

    static int mK = -1;
    static int mValue = -1;

    private static void searchTree(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        searchTree(treeNode.left);
        mK--;
        if (mK == 0) {
            mValue = treeNode.val;
        }
        searchTree(treeNode.right);
    }

    private static void zhiPrintProblem() {
        /**
         * 树结构
         *          1
         *        /   \
         *      2      3
         *    /  \   /
         *   4    5 6
         *       /
         *     7
         */
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode5.left = treeNode7;
        ArrayList<ArrayList<Integer>> list = zhiPrint(treeNode);
        System.out.printf("之字打印： ");
        for (ArrayList<Integer> integers : list) {
            for (Integer integer : integers) {
                System.out.printf(" " + integer);
            }
            System.out.printf(",");
        }
        System.out.println();
    }

    /**
     * 之字形打印，采用双端队列，区别于层序遍历采用的是普通队列，
     * 关键点：
     * 1、遍历队列时，使用for循环，i--形式，因为队列内容在变化，queue的size是不断变化的，所以倒着使用能保证循环老数据不循环新数据
     * 2、层序遍历时，直接pull；双端队列时，记得要remove操作
     *
     * @param treeNode
     * @return
     */
    private static ArrayList<ArrayList<Integer>> zhiPrint(TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(treeNode);
        while (!deque.isEmpty()) {
            if (deque.isEmpty()) {
                break;
            }
            //奇数行
            ArrayList<Integer> tmpList = new ArrayList<>();
            for (int i = deque.size(); i > 0; i--) {
                TreeNode treeNode1 = deque.removeFirst();
                tmpList.add(treeNode1.val);
                if (treeNode1.left != null) {
                    deque.addLast(treeNode1.left);
                }
                if (treeNode1.right != null) {
                    deque.addLast(treeNode1.right);
                }
            }
            allList.add(tmpList);
            //偶数行
            tmpList = new ArrayList<>();
            for (int j = deque.size(); j > 0; j--) {
                TreeNode treeNode1 = deque.removeLast();
                tmpList.add(treeNode1.val);
                if (treeNode1.right != null) {
                    deque.addFirst(treeNode1.right);
                }
                if (treeNode1.left != null) {
                    deque.addFirst(treeNode1.left);
                }
            }
            allList.add(tmpList);
        }
        return allList;
    }

    private static void treeDepthProblem() {
        /**
         * 树结构
         *          1
         *        /   \
         *      2      3
         *    /  \   /
         *   4    5 6
         *       /
         *     7
         */
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode5.left = treeNode7;
        int depth = treeDepth(treeNode);
        System.out.println("树的层数：" + depth);
    }

    /**
     * 利用递归，递归方法为获取树的层数，分别获取左子树层数和右子树层数，比较取大值，加上本层数1，就等于当前树节点的最大层数，结束条件是，当前树为空
     *
     * @param treeNode
     * @return
     */
    private static int treeDepth(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int left = treeDepth(treeNode.left);
        int right = treeDepth(treeNode.right);
        int max = Math.max(left, right);
        max += 1;
        return max;
    }

    private static void initTreeNode() {
        /**
         * 树结构
         *          1
         *        /   \
         *      2      3
         *    /  \   /  \
         *   4    5 6    7
         */
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;

        mTreeNode = treeNode;
    }

    private static void cengXuProblem() {
        // 1 2 3 4 5 6 7
        System.out.printf("层序： ");
        cengxu(mTreeNode);
        System.out.println();
    }

    private static void houXuProblem() {
        // 4 5 2 6 7 3 1
        System.out.printf("后序： ");
        houxu(mTreeNode);
        System.out.println();
    }

    private static void zhongXuProblem() {
        // 4 2 5 1 6 3 7
        System.out.printf("中序： ");
        zhongxu(mTreeNode);
        System.out.println();
    }

    private static void qianXuProblem() {
        // 1 2 4 5 3 6 7
        System.out.printf("前序： ");
        qianxu(mTreeNode);
        System.out.println();
    }

    /**
     * 层序遍历原理，利用queue先进先出的原理，将树的数据一层一层放入
     *
     * @param treeNode
     */
    private static void cengxu(TreeNode treeNode) {
        if (treeNode == null) {
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
            System.out.print(poll.val + " ");
        }
    }

    //左 -> 右 -> 根
    private static void houxu(TreeNode treeNode) {
        if (treeNode != null) {
            houxu(treeNode.left);
            houxu(treeNode.right);
            System.out.printf(treeNode.val + " ");
        }
    }

    //左 -> 根 -> 右
    private static void zhongxu(TreeNode treeNode) {
        if (treeNode != null) {
            zhongxu(treeNode.left);
            System.out.printf(treeNode.val + " ");
            zhongxu(treeNode.right);
        }
    }

    //根 -> 左 -> 右
    public static void qianxu(TreeNode treeNode) {
        if (treeNode != null) {
            System.out.print(treeNode.val + " ");// 当前节点
            qianxu(treeNode.left);
            qianxu(treeNode.right);
        }
    }

    public static void printTreeUtil(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.add(treeNode);
        while (!deque.isEmpty()) {
            for (int i = deque.size(); i > 0; i--) {
                TreeNode node = deque.poll();
                System.out.printf(node.val + "  ");
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
            }
            System.out.println();
        }
    }

    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

}
